package LearnAlgorithm.h_标准数学公式;

/*
x ≡ a1 (mod m1)					(1式)
x ≡ a2 (mod m2)					(2式)
x ≡ a3 (mod m3)					(3式)	(1,2,3式是所有的模方程)
对(1式)和(2式)看：
x = a1 + m1 * y1 				(4式)
x = a2 + m2 * y2 				(5式)
联立(4式)(5式)：
m1 * y1 - m2 * y2 = a2 - a1		(这是一个裴蜀等式ax + by = m)
可利用linearEquation(m1, -m2, a2-a1)求出y1的特解之一"y1_0"
把y1_0带入(4式)得x的特解之一x0：
x0 = a1 + m1 * y1_0
因为x有无限个，可以通过特解x0推出其他x，推出的方法是x0加m1与m2的最小公倍数(为什么需要加m1与m2的最小公倍数？死记硬背的)：
x = x0 + k * lcm(m1, m2) 		(k是整数；lcm(m1. m2)求出m1与m2的最小公倍数)(这是x的通解式子)
x的通解式子也可以写成下面的样子：
x ≡ x0 (mod (lcm(m1, m2)))		(6式)

然后我们对(3式)和(6式)看：
x = x0 + lcm(m1, m2) * k 		(7式)
x = a3 + m3 * y3 				(8式)
如此循环，直到所有的最初的模方程全部参与了计算.........

这种算法成为“逐级合并法”
 */
public class h一元线性同余方程组by逐级合并法also中国剩余定理also大衍求一术 {
	public static void main(String[] args) {
		long[] a = new long[] {2, 3, 2};
		long[] m = new long[] {3, 5, 7};
		try {
			long res = new h一元线性同余方程组by逐级合并法also中国剩余定理also大衍求一术().linearEquationGroup(a, m);
			System.out.println(res);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	/**
		传入的是所有模方程的“a”和“m”
		运用循环把所有的模方程参与运算
	 * @param a
	 * @param m
	 * @return
	 * @throws Exception
	 */
	public long linearEquationGroup(long[] a, long[] m) throws Exception {
		int len = a.length;
		if (len == 0 && a[0] == 0) {
			return m[0];
		}
		for (int i = 1; i < len; i++) {//每次循环都是当前模方程与上一个模方程；m1 * y1 - m2 * y2 = a2 - a1
			long a2_a1 = a[i] - a[i - 1];//a2 - a1
			long d = ExtGcd.linearEquation(m[i - 1], -m[i], a2_a1);//linearEquation(m1, -m2, a2 - a1)
			long x0 = a[i - 1] + m[i - 1] * ExtGcd.x;//x0 = a1 + m1 * y1_0；y1_0 = ExtGcd.x
			long lcm = (m[i - 1] * m[i]) / d;//lcm(m1, m2)；求m1与m2的最小公倍数
			
			
			a[i] = (x0 % lcm + lcm) % lcm;
			m[i] = lcm;
			//x = (x0 % lcm + lcm) % lcm ↔ x = x0 + k * lcm(m1, m2)  这一步获得一个正数特解x；
			//a[i] = x ↔ “这一步是更新a2”
			//m[i] = lcm ↔ “这一步是更新m2”
			//在逻辑中：
			//		原：
			//				x ≡ a1 (mod m1)					(1式)
			//				x ≡ a2 (mod m2)					(2式)
			//				x ≡ a3 (mod m3)					(3式)
			//		现：
			//				x ≡ x0 (mod (lcm(m1, m2)))  	(1式)
			//				x ≡ a3 (mod m3)					(2式)
			//在数组中：
			//				x ≡ a1 (mod m1)					(1式)
			//				x ≡ x0{替换了a2} (mod (lcm(m1, m2)){替换了m2})  	(2式)
			//				x ≡ a3 (mod m3)					(3式)
		}
		//所有模方程合并完之后,逻辑上只剩一个方程: x ≡ a[len-1] (mod m[len-1])
		//long d = linearEquation(1, m[len-1], a[len-1]);
//		System.out.println(a[len - 1]);//a[len - 1] = (a[len - 1] % m[len - 1]);
		return a[len - 1] % m[len - 1];//返回一元线性同余方程组中的x的解；其实写System.out.println(a[len - 1]);也可以
	}
	
	public static class ExtGcd {
		static long x;
		static long y;
		public static long gcdEx(long a, long b) {
			if (b == 0) {
				x = 1;
				y = 1;
				return a;
			}
			long res = gcdEx(b, a % b);
			long x1 = x;
			x = y;
			y = x1 - a / b * y;
			return res;
		}
		public static long linearEquation(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			long n = Math.abs(m / d);
//			x *= n;
//			y *= n;
			return d;
		}
		public static long linearEquationOriginalEquation(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			long n = Math.abs(m / d);
			x *= n;
			y *= n;
			return d;
		}
		public static long firstSolution(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			b = b / d;
			x = (x % b + b) % b;
			return x;
		}
		public static long inverseElement(long a, long n) throws Exception {
			linearEquation(a, n, 1);
			x = (x % n + n) % n;
			return x;
		}
	}
}
